/**
 * KMP算法-根据模式串计算next数组
 * @param {String} sub 模式串
 * @returns 对应的next数组
 */
function getNext(sub) {
	// 初始化
	let next = new Array(sub.length);
	next[0] = -1;
	next[1] = 0;
	let m = 0;
	let n = 1;
	// 开始判断sub[m]和sub[n]的情况
	while (n < sub.length - 1) {
		// 如果相等或者不相等但是m == -1时（无法再次级比较时）
		if (m === -1 || sub[m] === sub[n]) {
			m++;
			n++;
			next[n] = m;
		} else {
			// 不相等，次级比较
			m = next[m];
		}
	}
	return next;
}

/**
 * KMP算法 - 匹配子串在主串的位置
 * @param {String} main 主串
 * @param {String} sub 子串
 * @returns 子串在主串第一次出现的位置， 若匹配失败返回-1
 */
function KMPMatchIndexOf(main, sub) {
	// 先根据模式串求得next数组
	let next = getNext(sub);
	let i = 0;
	let j = 0;
	// 开始逐个比较
	while (i < main.length && j < sub.length) {
		// 如果当前比较的字符相等，则i，j后移一位比较下一个
		// 如果j被重定向至-1，说明模式串第一位就失配了，这时也只能把i，j后移一位才能继续比较
		if (j === -1 || main[i] === sub[j]) {
			i++;
			j++;
		} else {
			// 不相等，则重定向至next[j]
			j = next[j];
		}
	}
	// 比较完毕，如果说j现在大于子串的长度 - 1（正常情况下匹配完成后j=sub的最后一个字符的索引+1，恰好等于sub长度值，因为字符串第一个字符索引是0），说明子串全部匹配完成，匹配成功
	if (j > sub.length - 1) {
		return i - sub.length;
	} else {
		// 否则说明匹配失败
		return -1;
	}
}

// 测试一下
console.log(KMPMatchIndexOf('aaaaaaaaaaaaaaaaaaaaaaaaaaab', 'aaab'));